\section{methodology} \label{sec:methodology}

\subsection{Hash table \& Key size} \label{sec:method_hash} 

The number of base pairs of whole DNA sequence is about 3.15 billion. So, the
number of coordinate corresponding to the whole DNA sequence is also the same
with the number of base pairs of whole DNA sequence. About 12GBytes memory
capacity is needed just for preserving the coordinates in hash table. To reduce
the requirement of huge memory capacity to preserve the hash table, we divide
the whole DNA sequence to 22 hash tables based on the chromosomes. The memory
size to preserve the index of hash table is directly related to the key length,
i.e. total 10.5MByte is need for preserving the index of hash table,
corresponding to 10 base pairs length key and if we increase the number of key
size to 15 base pair length, then, we need 16Gbytes just for preserving the
index of hash table. Large table size also requires huge amount of time to
transfer data from files to main memory. There is one more consideration point
for choosing the key length as index. If we reduce the key length for index of
hash table, then, the number of coordinates corresponding to each index is
drastically increased. This means that it take long time to find out the
coordinate for retrieving the reference sequences for sting comparison, also it
requires a lot of time for Adjacency Filtering. The number of operations
required for Adjacency Filtering is proportional to log (the number of
coordinate corresponding to the index).
%Figure [?] shows the required time for
%Adjacency Filtering at the case 9 key lengths and 12 key lengths for index. 
The two factors, the requirement of memory capacity for hash table and the
searching time took for Adjacency Filtering, are tradeoff. In this work, we
choose 12 key lengths as index to balance these two factors. The key length of
index can be changeable to optimize hash table for the specific purpose or the
environmental change, i.e. the advent of huge memory size at low cost.\\

\subsection{Input fragment set} \label{sec:medhod_input}

The input fragments are selected from the substrings of the first chromosome of
Reference sequence. After that, the selected substrings are shuffled randomly
to eliminate the similarity between adjacency fragments and reduce the effect
of caching caused by the similarity of these adjacency fragments. These
randomization methods make the input set to be more near the real input
fragments. Total 1 million fragments are selected as input fragments set by
using these methods. The size of input fragment is 108ea base pair length.\\

\subsection{Hardware environment} \label{sec:method_hw}

For the evaluation of CPU version, we use Intel Sandybridge i7 with 16GB main
memory. For the GPU version, Nvidia Tesla C2070 with 6GB local memory (GDDR5)
is used. The block size of GPU version is 280ea and the number of thread per
block is 1000ea. Each block operates for just one input fragment and the
threads corresponding to each block are allocated for the test of each
coordinates corresponding to the fragment. For example, 280ea input fragments
are fetched at same time and they are shipped to GPU memory. In GPU, there are
14ea computational cores and each core can perform one block at one time. In
each GPU core, 1000ea threads can be generated for evaluate 1000ea coordinates.
The 32ea threads can be operated simultaneously. Table~\ref{table:tesla} shows
that the general specification of Nvidia Tesla C2070.\\

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{table}[h]
\begin{footnotesize}
\begin{center}
\begin{tabular}{|l|c|}
\hline

& \multirow{1}{2.5cm}{\centering Specification}	
\\ \hline
  \multirow{1}{4.0cm}{\centering Clock rate}
& \multirow{1}{2.5cm}{\centering 1147000}	
\\ \hline
  \multirow{1}{4.0cm}{\centering Global memory}
& \multirow{1}{2.5cm}{\centering 5.6GByte}			
\\ \hline
  \multirow{1}{4.0cm}{\centering Constant memory}
& \multirow{1}{2.5cm}{\centering 65.5KByte}			
\\ \hline
  \multirow{1}{4.0cm}{\centering Multiprocessor}
& \multirow{1}{2.5cm}{\centering 14ea}			
\\ \hline
  \multirow{1}{4.0cm}{\centering Shared memory / mp}
& \multirow{1}{2.5cm}{\centering 49.2KByte}			
\\ \hline
  \multirow{1}{4.0cm}{\centering Register / mp}
& \multirow{1}{2.5cm}{\centering 32.7KByte}			
\\ \hline
  \multirow{1}{4.0cm}{\centering Max threads / block}
& \multirow{1}{2.5cm}{\centering 1024}			
\\ \hline
  \multirow{1}{4.0cm}{\centering Max threads dimensions}
& \multirow{1}{2.5cm}{\centering 1024 / 1024 / 64}
\\ \hline
  \multirow{1}{4.0cm}{\centering Max grid dimensions}
& \multirow{1}{2.5cm}{\centering 65K / 65K / 65K}
\\ \hline

\end{tabular}
\caption{Nvidia Tesla C2070 Specification.}
\label{table:tesla}
\end{center}
\end{footnotesize}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
